public class UniquePaths {
    /*
    * 62. 不同路径
    * 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
    * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
    * 问总共有多少条不同的路径？
    *
    * 1 <= m, n <= 100
    * 题目数据保证答案小于等于 2 * 10^9
    * */
    public static void main(String[] args){

    }

    // 我的想法：到达右下角的路径取决于到达其上面一格的路径和到达其左边一格的路径的和
    public int mySolution(int m, int n){
        if(m == 1 || n == 1)
            return 1;
        // 确定dp数组及其含义，这里得用二维数组，dp[i][j]表示到达ij格的不同路径
        int[][] dp = new int[m][n];
        // 初始化数组
        dp[0][0] = 0;
        dp[0][1] = 1;
        dp[1][0] = 1;

        // 确定遍历顺序， 因为每格需要自己的上面格和左边格，我们采用一行一行遍历的方法，确保每格能被计算出来
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 确定递推公式
                if(i != 0)
                    dp[i][j] += dp[i-1][j];
                if(j != 0)
                    dp[i][j] += dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
